package medium;

import java.util.ArrayList;
import java.util.List;

/**
 * 994. 腐烂的橘子
 * 创建时间：2024-05-13 19:53
 * 地址：https://leetcode.cn/problems/rotting-oranges/description/?envType=daily-question&envId=2024-05-13
 */
public class 腐烂的橘子_994 {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向

    class Solution {
        public int orangesRotting(int[][] grid) {
            int n = grid[0].length; // 列长
            int m = grid.length; //    行高
            List<int[]> r = new ArrayList<>(); //已腐烂的橘子
            int fresh = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int x = grid[i][j];
                    if (x == 1) {
                        fresh++;
                    }
                    if (x == 2) {
                        r.add(new int[]{i, j});
                    }
                }
            }

            int ans = -1;
            while(!r.isEmpty()) {
                ans++;
                List<int[]> tmp = new ArrayList<>();
                for (int[] x : r) {
                    for (int[] direction : DIRECTIONS) {
                        int i = x[0] + direction[0];
                        int j = x[1] + direction[1];
                        if (i < m && i >= 0 && j >= 0 && j < n && grid[i][j] == 1)  {
                            tmp.add(new int[]{i, j});
                            grid[i][j] = 2;
                            fresh--;
                        }
                    }
                    r = tmp;
                }
            }
            return fresh > 0 ? -1 : Math.max(ans, 0);
        }
    }
}
